package leetcode_动态规划._07背包问题.完全背包;

/**
 * 组合总和 Ⅳ
 * 算法：
 *   回溯，超时
 */
public class _377 {
    public static void main(String[] args) {
        System.out.println(new _377().combinationSum4_huisu(new int[]{1, 2, 3}, 4));
    }

    // 先遍历背包，再遍历物品，这样物品的顺序的会不一样了
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (nums[j] <= i)
                    dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }

    public int combinationSum4_huisu(int[] nums, int target) {
        if (target == 0) {
            return 1;
        }
        int res = 0;
        for (int num : nums) {
            if (target >= num) {
                res += combinationSum4_huisu(nums, target - num);
            }
        }
        return res;
    }
}
